/**
 * @file HashFunctions.h
 * @brief hash functions
 * @detail
   two functions:
   1) unsigned PrimitiveTypeHash(T)
      for primitive types in C++:
          char, short, int, float, double, T* ...
   2) unsigned SuperStringHash(const char*, size_t)
      for string.
 * @author babear.wangz
 * @date 2011-04-02
 */

#ifndef ZST_HashFunctions_H
#define ZST_HashFunctions_H

#include "ZUtility.h"

template<size_t size> struct IntTypes;
template<> struct IntTypes<1>
{
    typedef int8_t SignedType;
    typedef uint8_t UnsignedType;
};
template<> struct IntTypes<2>
{
    typedef int16_t SignedType;
    typedef uint16_t UnsignedType;
};
template<> struct IntTypes<4>
{
    typedef int32_t SignedType;
    typedef uint32_t UnsignedType;
};
template<> struct IntTypes<8>
{
    typedef int64_t SignedType;
    typedef uint64_t UnsignedType;
};

// below is some integer hashfunctions,
// see: http://www.cris.com/~Ttwang/tech/inthash.htm
inline unsigned IntHash(uint8_t key8)
{
    unsigned key = key8;
    key += ~(key << 15);
    key ^= (key >> 10);
    key += (key << 3);
    key ^= (key >> 6);
    key += ~(key << 11);
    key ^= (key >> 16);
    return key;
}
inline unsigned IntHash(uint16_t key16)
{
    unsigned key = key16;
    key += ~(key << 15);
    key ^= (key >> 10);
    key += (key << 3);
    key ^= (key >> 6);
    key += ~(key << 11);
    key ^= (key >> 16);
    return key;
}
inline unsigned IntHash(uint32_t key32)
{
    unsigned key = key32;
    key += ~(key << 15);
    key ^= (key >> 10);
    key += (key << 3);
    key ^= (key >> 6);
    key += ~(key << 11);
    key ^= (key >> 16);
    return key;
}
inline unsigned IntHash(uint64_t key64)
{
    uint64_t key = key64;
    key += ~(key << 32);
    key ^= (key >> 22);
    key += ~(key << 13);
    key ^= (key >> 8);
    key += (key << 3);
    key ^= (key >> 15);
    key += ~(key << 27);
    key ^= (key >> 31);
    return static_cast<unsigned>(key);
}

/**
 * @fn PrimitiveTypeHash
 * @brief Hash function for C++ primitive types:
 * @brief   char, unsigned char, short, unsigned short
 * @brief   int, unsigned int, long, unsigned long
 * @brief   int*_t, uint*_t, float, double, T*
 * @author babear.wangz
 * @date 2011-04-02
 */
template<typename T>
unsigned PrimitiveTypeHash(T key)
{
    return
        IntHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key));
}

#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
    || defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__)
#define get16bits(d) (*((const uint16_t*)(d)))
#endif
#if !defined(get16bits)
#define get16bits(d) ((((uint32_t)(((const uint8_t*)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t*)(d))[0]))
#endif
/**
 * @fn SuperStringHash
 * @brief http://www.azillionmonkeys.com/qed/hash.html
 * @author babear.wangz
 * @date 2011-04-02
 */
unsigned SuperStringHash(const char* data, int len)
{
    uint32_t hash = len, tmp;
    int rem;
    if (len <= 0 || data == NULL) return 0;
    rem = len & 3;
    len >>= 2;// divided by 4
    // main loop
    for (; len > 0; len--) {
        hash += get16bits(data);
        tmp = (get16bits(data+2) << 11) ^ hash;
        hash = (hash << 16) ^ tmp;
        data += 2*sizeof(uint16_t);
        hash += hash >> 11;
    }
    // handle end cases
    switch (rem) {
    case 3: 
        hash += get16bits(data);
        hash ^= hash << 16;
        hash ^= data[sizeof(uint16_t)] << 18;
        hash += hash >> 11;
        break;
    case 2:
        hash += get16bits(data);
        hash ^= hash << 11;
        hash += hash >> 17;
        break;
    case 1:
        hash += *data;
        hash ^= hash << 10;
        hash += hash >> 1;
    }
    // force "avalanching" of final 127 bits
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;
    return static_cast<unsigned>(hash);
}

#endif

